Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Ranking- k: effective subspace dominating query algorithm
LI Qiusheng, WU Yadong, LIN Maosong, WANG Song, WANG Haiyang, FENG Xinmiao
Journal of Computer Applications    2015, 35 (1): 108-114.   DOI: 10.11772/j.issn.1001-9081.2015.01.0108
Abstract522)      PDF (1078KB)(667)       Save

Top-k dominating query algorithm requires high consumption of time and space to build combined indexes on the attributes, and the query accuracy is low for the data with same attribute values. To solve these problems, a Ranking-k algorithm was given in this paper. The proposed Ranking-k algorithm is a new subspace dominating query algorithm combining the B+-trees with probability distribution model. Firstly, the ordered lists for each data attribute were constructed by the B+-trees. Secondly, the round-robin scheduling algorithm was used to scan ordered attribute lists satisfying skyline criterion. Some candidate tuples were generated and k end tuples were obtained. Thirdly, the dominated scores of end tuples were calculated by using the probability distribution model according to the generated candidate tuples and end tuples. Through iterating the above process, the optimal query results were obtained. The experimental results show that the overall query efficiency of the proposed Ranking-k algorithm is improved by 94.43% compared with the Basic-Scan Algorithm (BSA) and by 7.63% compared with the Differential Algorithm (DA), and the query results of Ranking-k algorithm are much closer to theoretical values in comparison of the Top-k Dominating with Early Pruning (TDEP) algorithm, BSA and DA.

Reference | Related Articles | Metrics